The Google File System

论文基本信息

声明

本文为本人原创，未经授权严禁转载。如需转载需要在文章最前面注明本文原始链接。

摘要

这篇文章主要介绍了Google设计的一种新型文件系统，以及在设计过程中遇到的一些问题和解决方案。：

• 解决Linux中单个读写锁的问题：

  • 作者们发现了一个单一的读写锁，在轻负载下导致系统出现短暂的超时。
  • 经过深入调查后发现，这个单个锁会阻止主网络线程将新数据映射到内存中，而磁盘线程则正在将之前数据页映射进内存。
  • 通过使用pread()代替mmap()来解决这个问题，尽管这需要额外的复制操作。

• 实现高吞吐量：

  • 文章强调了设计的目标是为许多并发读者和写者提供高性能。
  • 设计中将控制文件系统（由主服务器管理）与数据传输（直接在客户端和存储服务器之间进行）分离开来。
  • 通过对主服务器的最小化参与和chunk lease机制（将数据修改权委派给primary replicas），实现了简单而不会成为瓶颈的集中式主服务器。
  • 作者相信，未来在网络堆栈方面的改进可以进一步提高单个客户端的写入吞吐量。

• 重新审视传统文件系统假设：

  • 作者们从当前应用工作负载和技术环境的角度出发，重新审视了传统的文件系统假设。
  • 他们的观察促使他们在设计空间中选择了不同的点。
  • 对待组件故障的态度是以常态看待，优化适用于大文件，通常用于追加写入（可能同时进行）和随后读取（通常是顺序）。
  • 扩展和放宽标准文件系统接口以改善整体系统性能。

综上所述，这篇文章介绍了一种新型的文件系统设计，以及在设计过程中的一些挑战和解决方案。

研究目标

假设

• 该系统由许多经常发生故障的廉价商品组件构建而成。它必须持续监视自身并在例行程序中检测、容忍并迅速从组件故障中恢复。
• 该系统存储适量的大文件。我们预计有几百万个文件，每个文件通常大小为 100 MB 或更大。多 GB 文件是常见情况，应高效管理。必须支持小文件，但我们无需对其进行优化。
• 工作负载主要由两种读取组成：大量的顺序读取和少量的随机读取。在顺序读取中，单个操作通常读取数百 KB，更常见的是 1 MB 或更多。来自同一客户端的连续操作通常会读取文件的一个连续区域。小型随机读取通常在某个任意偏移量处读取几 KB。注重性能的应用程序通常会批量处理并对其小读取进行排序，以稳定地推进文件，而不是来回读取。
• 工作负载还具有许多大的顺序写入，这些写入会将数据追加到文件。典型操作大小与读取操作的大小相似。一旦写入，就很少再次修改文件。支持在文件中的任意位置进行小写入，但不一定是高效的。
• 系统必须有效地实现对同时追加到同一文件的多个客户端的明确定义的语义。我们的文件通常用作生产者消费者队列或多路合并。数百个生产者（每台机器运行一个）会同时追加到一个文件。具有最少同步开销的原子性是必不可少的。该文件可能会稍后读取，或者消费者可能同时正在读取该文件。
• 高持续带宽比低延迟更重要。我们的大多数目标应用程序都非常重视以高速度批量处理数据，而很少有应用程序对单个读或写有严格的响应时间要求。

架构

GFS（Google File System）集群由一个主服务器和多个块服务器构成，客户端可通过用户级服务器进程在Linux机器上访问。文件被划分为固定大小（64MB）的块，并通过唯一的64位块句柄进行标识，每个块在多个块服务器上复制存储以保证可靠性，默认情况下保留三个副本。

主服务器负责维护整个文件系统的元数据，包括命名空间、访问控制信息、文件到块的映射以及块的位置信息（不需要持久化存储，可以从chunkserver收集），同时管理如块租约、垃圾回收和块迁移等系统活动。主服务器与块服务器之间定期通过心跳消息通信以发送指令和收集状态。

GFS客户端实现文件系统API并与主服务器及块服务器交互，完成应用程序的数据读写请求。客户端直接与块服务器进行带有数据的通信，而所有元数据操作则通过主服务器进行。由于不支持POSIX API，因此无需连接Linux vnode层。客户端和块服务器均不缓存文件数据，但客户端会缓存元数据以提高效率。

在进行简单读取操作时，客户端首先根据文件名和字节偏移量计算出对应的块索引，然后向主服务器请求包含文件名和块索引的信息。主服务器回复块句柄和副本位置后，客户端缓存此信息并直接与块服务器交互读取数据。后续对同一块的读取无需再次与主服务器交互，除非缓存信息过期或文件重新打开。此外，客户端可以请求额外的块信息以减少未来的交互次数。

一致性模型

状态理解

GFS采用 relaxed consistency模型。
GFS的一致性模型有两个含义：一致性和defined region。所谓一致性比较好理解，就是通常高并发写时的一致性。
GFS对defined region的定义是：在同一个区域中的多个客户端的同时写入，最终结果只会反映出某个客户端的完整的写入操作。在一个region中，一致性并不能保证该区域是被定义的。
undefined region有两种情况：

1. 当并发成功的数据更改发生时，由于不同更改操作可能同时对同一文件区域进行写入，结果混合了多个更改的片段，导致该区域的数据内容不能唯一对应到任何一个单独的变更操作。这样的区域虽然从一致性角度看是保持一致的（所有客户端看到同样的数据），但并不能确切地表示任何单个写入操作所期望的结果，因此称其为“未定义”。

2. 如果某个文件数据更改操作失败，这可能会破坏数据的一致性，使得不同客户端在不同的时间点读取同一区域时，可能会看到不同的数据内容。这种不一致的状态下，文件区域同样被视为未定义。

改写与追加操作可能造成的系统状态

改写

之所以不同chunk改写的执行顺序不一定相同是因为，不同chunk选定的primary chunkserver是有可能不同的。

追加

为了保证追加操作的原子执行，设计了以下的限制：

系统交互

租约与mutation顺序

一次mutation是指一次对chunk内容或者元数据的修改操作。每个mutation在所有chunk的副本上执行。我们使用租约来维护所有副本之间的一致mutation顺序。主节点将chunk租约授予其中一个副本，我们将其称为主要副本。主要副本为chunk中的所有mutation选择一个序列顺序。所有副本在应用mutation时遵循这个顺序。因此，全局mutation顺序首先由主节点选择的租约授予顺序定义，并在租约内由主要副本分配的序列号定义。租约机制旨在最小化主节点的管理开销。租约的初始超时时间为60秒。然而，只要chunk正在发生mutation，主要副本就可以无限期地向主节点请求并通常收到延期授权。这些请求被附加到主节点与所有chunkservers定期交换的心跳消息上。主节点有时可能会尝试在租约到期之前撤销租约（例如，当主节点希望禁用正在重命名的文件上的mutation时）。即使主节点失去与主要副本的通信，也可以在旧租约过期后安全地将新租约授予另一个副本。

1. 客户端请求主服务器查询当前哪个chunkserver持有对所请求的chunk的租约。如果都没有，那么主服务器就会选择一个副本授予租约;
2. 主服务器返回主副本和从副本的位置（控制数据）。客户端缓存这些信息直到副本服务器不可用或者租约到期；
3. 客户端将数据推送到所有副本。客户端可以以任意顺序执行此操作。每个块服务器将在内部LRU缓冲缓存中存储数据，直到数据被使用或老化淘汰。通过解耦数据流和控制流，我们可以根据网络拓扑调度昂贵的数据流，而不考虑哪个块服务器是主服务器，从而提高性能。第3.2节将进一步讨论这个问题。
4. 一旦所有副本确认接收到数据，客户端会向主副本发送写入请求。该请求标识之前推送给所有副本的数据。主副本为接收到的所有变更（可能来自多个客户端）分配连续的序列号，从而提供必要的串行化。它按照序列号顺序将其自身的本地状态应用这些变更。
5. 主副本将写入请求转发给所有从属副本。每个从属副本按照主服务器分配的相同序列号顺序应用变更。
6. 所有从属副本均回复主副本，表明它们已完成该操作。
7. 主副本回复客户端。在任何副本上遇到的任何错误都会报告给客户端。在出现错误的情况下，写入可能已在主副本及任意从属副本子集上成功完成。（如果在主副本上失败，则不会为其分配序列号并转发。）此时认为客户端请求已失败，并且修改过的区域处于不一致状态。我们的客户端代码通过重试失败的变更来处理此类错误。它会在步骤（3）至（7）之间尝试几次，然后再退回到写入开始时重新尝试。
   如果应用程序的写操作过大或跨越了数据块边界，GFS客户端代码会将其拆分为多个写操作。这些写操作均遵循上述描述的控制流程，但可能会与其他客户端并发操作交错执行并被覆盖。因此，共享文件区域最终可能包含来自不同客户端的片段，尽管副本是相同的，因为各个操作在所有副本上按相同顺序成功完成。这样一来，文件区域保持了一致性。

控制流与数据流分离：值得注意的是，尽管master向客户端分配了primary chunkserver,但是在进行数据传递时，客户端是把数据就近传递给了chunkserver,然后由该chunkserver分发给其他的chunkserver。当且仅当，客户端发送的是控制数据时才需要把数据发送给primary chunkserver,这也就是上述过程的第4步。

atomic record appends

为了保证追加操作的原子执行，设计了以下的限制：

snapshot

采用写时复制技术实现。
当主服务器接收到快照请求时，首先撤销即将进行快照的文件中所有未处理的租约，确保之后对这些块的任何写入操作都需要与主服务器交互以找到租约持有者。这样主服务器就有机会先创建新块的副本。撤销租约或租约到期后，主服务器将该操作记录到磁盘日志，并通过复制源文件或目录树的元数据将其应用到内存状态。新创建的快照文件指向与源文件相同的块。

在快照操作后，客户端首次尝试写入块C时，会向主服务器发送请求以查找当前租约持有者。主服务器注意到块C的引用计数大于1，此时它不会立即回复客户端请求，而是选择一个新的块句柄C'。主服务器随后要求每个存储有块C当前副本的chunkserver创建名为C'的新块。通过在同一chunkserver上创建新块。

master operation

主服务器在分布式文件系统中扮演核心角色，它负责执行所有的命名空间操作，并对系统范围内的数据块副本进行全面管理。具体而言，主服务器会进行块副本的放置决策，创建新的数据块及其副本，并通过协调多种全系统活动来确保所有数据块保持充分复制，平衡各个chunk服务器之间的负载，以及有效回收未使用的存储空间。接下来将针对上述各项任务展开详细讨论。

namespace operation

在GFS中，namespace是指：文件系统组织方式和结构的逻辑化表示。It serves as a lookup table that maps full pathnames of files and directories to their corresponding metadata. This means that instead of using a per-directory data structure listing all files within it, as seen in many traditional file systems, GFS maintains a compressed in-memory representation where each node in the tree (which can be an absolute file or directory name) is associated with a read-write lock.

使用读写锁以确保适当的串行化。读写锁可以保证高并发。例如两个客户端在同一目录下同时创建两个不同的文件，那么他们都持有对目录路径节点的读锁和对文件的写锁，二者不会冲突。

垃圾回收

在Google文件系统（GFS）中，当一个文件被删除时，并不会立即回收其物理存储空间。相反，它在文件和数据块级别采用了惰性垃圾回收机制，这一机制简化了系统并提高了可靠性。在删除过程中，主服务器会记录该事件，但并不会立即回收资源，而是将文件重命名为一个包含删除时间戳的隐藏名称。这个被重命名的文件在一个可配置的时间窗口内（默认为三天）仍可以访问和恢复。当隐藏文件在常规扫描期间最终从命名空间中移除时，其元数据会被擦除，从而切断与所属数据块的链接。主服务器还会通过类似的扫描来识别并删除孤立的数据块。

在编程语言中通常较为复杂的分布式垃圾回收，在GFS中由于集中管理数据块引用和副本（作为Linux文件存储在数据块服务器上）而得以简化。任何主服务器未知的副本都被视为垃圾。

GFS的垃圾回收方法具有以下优势：

1. 简单性和可靠性：通过统一清理未知或未使用的副本，有效地应对分布式系统中的潜在组件故障。
2. 效率：存储回收被整合到主服务器的后台任务中，以批量方式进行，并且仅在主服务器有剩余容量时执行，确保对高优先级客户端请求能做出迅速响应。
3. 安全防护：延迟回收存储空间起到了防止意外永久删除的安全保障作用。

然而，这种方法也存在一些缺点。在存储空间紧张时，延迟回收可能影响存储优化。为解决这一问题，GFS针对明确删除的文件加快了回收速度，并允许用户根据目录树定制复制和回收策略。例如，用户可以设置特定目录存储不进行复制的数据块，而在这些区域中被删除的文件将立即永久移除。

stale replica detection

在分布式存储系统中，识别陈旧副本至关重要，这是为了确保数据一致性。该过程如下：

1. 每个数据块都有一个由主服务器管理的版本号。这个版本号有助于识别该块的副本是否为最新或已过时。

2. 当主服务器向某个数据块授予新的租约（实质上是允许客户端写入该块）时，它会递增该块的版本号，并通知所有最新的副本，这些副本会在任何客户端写入操作发生前，在其持久化状态中记录这一更新后的版本。

3. 若某个数据块服务器出现故障并离线，由于停机期间缺少变更操作，其上的副本可能变得陈旧。当该块服务器重启并向主服务器报告其托管的数据块及其关联的版本号时，主服务器通过比较上报的版本与记录进行比对，从而识别出陈旧副本。

4. 如果上报的版本号高于主服务器所持有的版本，主服务器则假设先前未能正确更新版本，并将较高版本视为最近版本。

5. 主服务器通过垃圾回收机制定期移除陈旧副本。在此之前，在响应有关数据块信息的客户端请求时，主服务器会忽略陈旧副本，实际上将其视为不存在。

6. 为进一步确保数据一致性，主服务器在与客户端和块服务器通信时包含数据块版本号。例如，在告知客户端哪个块服务器持有租约或将指令发送给块服务器从另一个块服务器克隆数据块时，接收方会在执行前验证版本号。这样可以确保所有操作都涉及访问数据块的最新版本。

Fault Tolerance

高可用

• 快恢复
• chunk replication：默认每一个块都有三个副本。
• master replication: 只有所有Master副本上记录状态改变的日志都被刷新到磁盘上，该改变才会被提交。

master高可用

• master的三类元数据中，namespace和文件与chunk的对应关系，因为只在master中存在是必须要持久化的，也自然是要保证其高可用的。
• GFS在正在使用的master称为primary master。在primary master:之外，GFS还维持一个 shadow master作为备份。
• Master在正常运行时，对元数据做的所有修改操作，都要先记录日志(WAL),再真正去修改内存中的元数据。 primary masters会实时向shadow masterl同步WAL,只有shadow master同步日志完成，元数据修改操作才算成功。

chunkserver高可用

默认每一个块数据都有三个副本。在写入时如何保证chunkserver的副本的数据写入已经在#^ff3212中进行了介绍。

• GFS维持每个chunk的校验和，读取时可以通过校验和进行数据的校验。如果校验和不匹配 chunkserver会反馈给master处理，master会选择其他副本进行读取，并重建此chunki副本。
• 为了减少对master的压力，GFS采用了一种租约(Lease)机制，把文件的读写权限下放给某一个chunk副本。
• Master可以把租约授权给某个chunk副本，我们把这个chunki副本称为orimary,在租约生效的一段时间内，对这个chunk的写操作直接由这个副本负责，租约的有效期一般为60秒。
• 租约的主备只决定控制流走向，不影响数据流。

数据完整性

谷歌文件系统（GFS）在其存储数据的块服务器上使用校验和来保证数据完整性，这些服务器以64KB的块大小存储数据，并配有相应的32位校验和。由于硬盘故障频繁且由于原子记录追加可能导致合法但不一致的副本，因此每个块服务器都会独立地使用校验和验证其存储数据的完整性。当客户端或其他块服务器请求读取操作时，块服务器首先会检查重叠数据块的校验和，然后才返回任何数据，从而防止了数据损坏的传播。如果检测到不匹配，块服务器会向主节点报告，随后主节点通过从有效副本克隆来促进恢复过程。

校验和验证过程对读取性能的影响较小，这得益于一些优化措施，如将读取操作与校验和块边界对齐、在查找和比较过程中避免I/O操作以及将校验和计算与I/O操作重叠进行。写入操作也得到了优化，特别是对于追加操作，此时校验和会递增更新，确保在下次读取该块时能及时发现并处理损坏问题。对于覆盖已有数据的写入操作，系统会谨慎地验证并更新校验和，以防止潜在的数据损坏被掩盖。

在低活动期间，块服务器会主动扫描并验证非活动的数据块，以便检测未察觉到的损坏情况。一旦发现损坏，主节点会创建一个新的无损副本，并移除已损坏的副本，确保系统中准确跟踪有效的数据块副本状态。

实验

结论

未来与展望

强相关文献

请 Ta 喝咖啡 ☕️